package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *  寻找重复的子树
 * 给定一棵二叉树 root，返回所有重复的子树。
 *
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-duplicate-subtrees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution652 {
    /**
     * 将节点进行序列化。
     * @param root
     * @return
     */
    private Map<String,Integer> memo = new HashMap<>();
    private List<TreeNode> result = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        travel(root);
        return result;
    }
    // 序列化二叉树
    // 使用先序遍历的方式进行 序列化
    private String travel(TreeNode root) {
        if (root==null){
            return "#";
        }
        StringBuffer sb = new StringBuffer();
        sb.append(root.val).append(",").append(travel(root.left)).append(",")
                .append(travel(root.right));
        Integer containtfre = memo.getOrDefault(sb.toString(), 0);
        if (containtfre ==1){
            result.add(root);
        }
        memo.put(sb.toString(),containtfre+1);
        return sb.toString();
    }
    @Test
    public void runTest(){
        TreeNode treeNode = new TreeNode(0);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode22 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode33 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode.left=treeNode1;
        treeNode1.left = treeNode2;
        treeNode2.left = treeNode3;
        treeNode.right = treeNode5;
        treeNode5.left=treeNode22;
        treeNode22.left = treeNode33;
        String travel = travel(treeNode);
        System.out.println(travel);
        System.out.println(findDuplicateSubtrees(treeNode));
    }
}
